package networkDelayTime

import "math"

/**
有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

*/

/*
从 k 点出发，所有点都被访问到的最短时间，将问题转换一下其实就是求从 k 点出发，到其他点 x 的最短距离的最大值。
*/
func networkDelayTime(times [][]int, n int, k int) int {
	var maxNum = math.MaxInt64 / 2
	// 初始化邻接矩阵
	edge := make([][]int, n)
	for i := range edge {
		edge[i] = make([]int, n)
		for j := range edge[i] {
			edge[i][j] = maxNum
		}
	}
	// 存图
	for _, value := range times {
		s := value[0] - 1
		e := value[1] - 1
		w := value[2]
		edge[s][e] = w
	}

	//Dijkstra()
	// 存放起点到各个点的最短距离
	dist := make([]int, n)
	for i := range dist {
		dist[i] = maxNum
	}
	dist[k-1] = 0 // 以K为起点
	used := make([]bool, n)
	for i := 0; i < n; i++ {
		x := -1
		// 每次从未找过的点中选择一个最短的起点到该点的点
		for index, value := range used {
			if !value && (x == -1 || dist[index] < dist[x]) {
				x = index
			}
		}
		// 标记该点
		used[x] = true
		// 遍历x可达到的点，并更新dist
		for y, time := range edge[x] {
			dist[y] = min(dist[y], dist[x]+time)
		}
	}
	// 遍历答案
	ans := 0
	for _, d := range dist {
		if d == maxNum {
			return -1
		}
		ans = max(ans, d)
	}
	return ans

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
